In computer science, an SLR grammar is a class of formal grammar that can be parsed by a simple LR parser.
Contents |
A rule of the form B → y. within a state of a SLR(1) automaton is said to be irreducible or in a reduce state because it has been completely expanded and is incapable of undergoing any shift transition. Rules in this state will have a dot (the current look-ahead position) located at the rightmost end of its RHS (Right Hand Side).
A Grammar is said to be SLR(1) if and only if, for each and every state s in the SLR(1) automaton, none of the following conditions are violated:
1. For any reducible rule A → a.Xb in state s (where X is some terminal), there must not exist some irreducible rule, B → y. in the same state s such that the follow set of B contains the terminal X. In more formal terms, the intersection of set containing the terminal X and the follow set of B must be empty. Violation of this rule is a Shift-Reduce Conflict.
2. For any two complete items A → a. and B → b. in s, Follow(A) and Follow(B) are disjoint (their intersection is the empty set). Violation of this rule is a Reduce-Reduce Conflict.
A grammar is said to be SLR(1) if the following Simple LR parser algorithm results in no ambiguity.
1. If state s contains any item of the form A -> a.Xb, where X is a terminal, and X is the next token in the input string, then the action is to shift the current input token onto the stack, and the new state to be pushed on the stack is the state containing the item A -> aX.b.
2. If state s contains the complete item A -> y., and the next token in the input string is in Follow(A), then the action is to reduce by the rule A -> y. A reduction by the rule S' -> S, where S is the start state, is equivalent to acceptance; this will happen only if the next input token is $. In all other cases, the new state in computed as follows. Remove the string y and all of its corresponding states from the parsing stack. Correspondingly, back up in the DFA to the state from which the construction of y began. By construction, this state must contain an item of the form B -> a.Ab. Push A on to the stack, and push the state containing the item B -> aA.b.
3. If the next input token is such that neither of the above two cases apply, an error is declared.